/**
 * 初始哈希表
 */
const map = new Map<number, string>();
/**添加操作 */
map.set(12836, '小哈');
map.set(15937, '小啰');
map.set(16750, '小算');
map.set(13276, '小法');
map.set(10583, '小鸭');
console.info('\n添加完成后，哈希表为\nKey -> Value');
console.info(map);
/**检查操作 */
let hasKey = map.has(16750);
console.info(`检查Key为16750是否存在${hasKey}`);

/**修改操作 */
map.set(16750, '小算子');
console.info('\n修改Key为16750的值为小算子后，哈希表为\nKey -> Value');

/**获取map大小 */
let mapSize = map.size;
console.info(`\n哈希表大小为${mapSize}`);

/**查询操作 */
let keyName = map.get(10583);
console.info(`查询Key为10583的值为${keyName}`);

/**删除操作 */
map.delete(15937);
console.info('\n删除Key为15937后，哈希表为\nKey -> Value');
console.info(map);

/**遍历哈希表 */
map.forEach((value, key) => {        // 方式一
  console.info(`Key为${key}的值为${value}`);
})
for (const [k, v] of map.entries()) { // 方式二
  console.info(`Key为${k}的值为${v}`);
}
for (const k of map.keys()) {        // 遍历key
  console.info(`Key为${k}的值为${map.get(k)}`);
}
for (const v of map.values()) {      // 遍历value
  console.info(`值为${v}`);
}

/**
 * 哈希表简单实现
 */
class Pair {
  public key: number;
  public value: string;
  constructor(key: number, value: string) {
    this.key = key;
    this.value = value;
  }
}
// 基于数组实现哈希表
class HashTable {
  private readonly buckets: Array<Pair | null>;
  // private readonly bukkets: (Pair | null)[];
  constructor() {
    this.buckets = new Array(100).fill(null);
  }
  /**哈希函数 */
  private hashFunc(key: number): number {
    return key % 100;
  }
  /** 查询操作 */
  public get(key: number): string | null {
    let index = this.hashFunc(key);
    let pair = this.buckets[index];
    if (pair === null) return null;
    return pair.value;
  }
  /**添加操作 */
  public set(key: number, value: string): void {
    let index = this.hashFunc(key);
    this.buckets[index] = new Pair(key, value);
  }
  /**删除操作 */
  public delete(key: number): void {
    let index = this.hashFunc(key);
    // null代表删除
    this.buckets[index] = null;
  }
  /**获取所有键值对 */
  public getAll(): Array<Pair | null> {
    let arr: Array<Pair | null> = [];
    for (let i = 0; i < this.buckets.length; i++) {
      if (this.buckets[i] !== null) {
        arr.push(this.buckets[i]!);
      }
    }
    return arr;
  }
  /**获取所有的键 */
  public getAllKeys(): Array<number | undefined> {
    let arr: Array<number | undefined> = [];
    for (let i = 0; i < this.buckets.length; i++) {
      if (this.buckets[i] !== null) {
        arr.push(this.buckets[i]!.key);
      }
    }
    return arr;
  }
  /**获取所有的值 */
  public getAllValues(): Array<string | undefined> {
    let arr: Array<string | undefined> = [];
    for (let i = 0; i < this.buckets.length; i++) {
      if (this.buckets[i] !== null) {
        arr.push(this.buckets[i]!.value);
      }
    }
    return arr;
  }
  /**打印哈希表 */
  public print(): void {
    let arr = this.getAll();
    for (const element of arr) {
      console.info(`${element?.key} : ${element?.value}`);
    }
  }
}
/** 哈希冲突与扩容 */
// 哈希冲突：当两个不同的key经过哈希函数计算后得到相同的index时，就会发生哈希冲突
// 哈希冲突的解决方法：开放寻址法、链表法
// 哈希表的元素数量除以桶数量得到的比率通常被称为负载因子（Load Factor）。这个比率是衡量哈希表填充程度的一个指标，对于哈希表的性能有着重要影响：
// 较低的负载因子意味着哈希表中有相对较多的空桶，这可以减少冲突的发生，但会浪费存储空间。
// 较高的负载因子意味着哈希表中桶的使用率较高，可能会增加冲突的概率，降低查找效率，但能够更有效地利用存储空间。
// 也常作为哈希表扩容的触发条件



